package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

/**
 * 使用最少步数
 * see 55
 * 怎么总往单调栈上想呢, 单调栈也不是最优解啊.
 * <p>
 * 之前两个写法都是从右往左想;
 * <p>
 * 题解是从左往右, 利用递归, 也有单调:
 * <p>
 * https://leetcode.com/problems/jump-game-ii/discuss/18014/Concise-O(n)-one-loop-JAVA-solution-based-on-Greedy
 * <p>
 * https://www.bilibili.com/video/BV1aW411m79s?from=search&seid=15737798155215496918
 * 43:30
 * <p>
 * 从第1步开始, 思考每一步能覆盖到的范围.
 * [2, 3, 1, 1, 4]为例
 * 第一步能覆盖 i0, i1 或者说i0, i1一步就能迈到.
 * i2,3,4两步就能迈到
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC45_2 implements Greedy {
    public int jump(int[] A) {
        int jumps = 0, curEnd = 0, curFarthest = 0;
        for (int i = 0; i < A.length - 1; i++) {
            curFarthest = Math.max(curFarthest, i + A[i]);
            if (i == curEnd) {
                jumps++;
                curEnd = curFarthest;
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        System.out.println(new LC45_2().jump(new int[]{2, 1, 1, 1, 4}));
//        System.out.println(new LC45_2().jump(new int[]{2, 3, 1, 1, 4}));
//        System.out.println(new LC45_2().jump(new int[]{2, 2, 1, 2, 4}));
    }
}
